// https://leetcode.cn/problems/combinations/

// 题干：给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
//       你可以按 任何顺序 返回答案。

// 示例：输入：n = 4, k = 2
//       输出：[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]

// 碎语：本题中不用太多全局变量，直接传参数就行，因为选过了一个数，不可能会继续选

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    vector<vector<int>> ret;
    vector<int> path;
    int n, k;
public:
    vector<vector<int>> combine(int _n, int _k)
    {
        n = _n, k = _k;
        dfs(1);

        return ret;
    }

    void dfs(int start)
    {
        if (path.size() == k){
            ret.push_back(path);
            return ;
        }

        for (int i = start ; i <= n ; i++){
            path.push_back(i);
            dfs(i + 1);
            path.pop_back();
        }
    }
};

int main()
{
    Solution sol;

    vector<vector<int>> index = sol.combine(4, 3);
    for (const auto& arr : index){
        for (const auto& num : arr){
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}